package main

import (
	"fmt"
	. "local/datastructure/graph/am"
)

/**
https://www.bilibili.com/video/av54668527?from=search&seid=17549442407179114349
https://blog.csdn.net/jnu_simba/article/details/8872626
*/

func main() {
	G := AMGraph{}
	D, P := shortestpath_floyd(G)
	for i := 0; i < G.NumArcs; i++ {
		for j := i + 1; j < G.NumVers; j++ {
			fmt.Print("v", i)
			k := P[i][j]
			for k != j {
				fmt.Print("v", k, "->")
				k = P[k][j]
			}
			fmt.Println("v", j)
		}
	}
}

func shortestpath_floyd(G AMGraph) ([][]int, [][]int) {
	D := createMetrix(G.NumVers)
	P := createMetrix(G.NumVers)
	for i := 0; i < G.NumArcs; i++ {
		for j := 0; j < G.NumVers; j++ {
			D[i][j] = G.Arcs[i][j]
			P[i][j] = j
		}
	}
	for k := 0; k < G.NumVers; k++ {
		for i := 0; i < G.NumArcs; i++ {
			for j := 0; j < G.NumVers; j++ {
				if D[i][k]+D[k][j] < D[i][j] {
					D[i][j] = D[i][k] + D[k][j]
					P[i][j] = P[i][k]
				}
			}
		}
	}
	return D, P
}

func createMetrix(n int) [][]int {
	o := [][]int{}
	for i := 0; i < n; i++ {
		o = append(o, make([]int, n))
	}
	return o
}
